package leetcode.code1377;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public double frogPosition(int n, int[][] edges, int t, int target) {
		List<List<Integer>> nexts = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] e : edges) {
			int a = e[0], b = e[1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		Double[] been = new Double[n + 1];
		int[] times = new int[n + 1];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);// 小心，这不是0
		been[1] = 1d;
		times[1] = 0;
		int time = 0;
		while (!queue.isEmpty() && been[target] == null && time <= t) {
			int cur = queue.poll();
			time = ++times[cur];
			List<Integer> next = nexts.get(cur);
			int to = cur == 1 ? next.size() : next.size() - 1;
			double ans = been[cur] / to;
			for (int nxt : next) {
				if (been[nxt] == null) {
					times[nxt] = time;
					been[nxt] = ans;
					queue.add(nxt);
				}
			}
		}
		if (been[target] == null) {// 时间耗尽，未抵达
			return 0;
		}
		if (times[target] == t) {// 正好抵达
			return been[target];
		}
		List<Integer> next = nexts.get(target);
		for (int nxt : next) {
			if (been[nxt] == null) {
				return 0;
			}
		}
		return been[target];
	}

	@Override
	public void debug4() {
		System.out.println(this.frogPosition(7, H.str2array1("[[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]"), 2, 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
